In data center environments, rack units may house many server devices. Each server device may be configured to host one or more physical or virtual host (virtual machine) devices. The servers in the rack units are connected to top-of-rack (ToR) switch devices. The ToR switches, in turn, are connected to other ToR switches via a spine switch or spine fabric. The ToR switches and spine switches form a physical underlay network, which may be used by multiple tenant networks that exchange data communications between host devices (physical and/or virtual) in different rack units. For example, packets of data communications may be sent from a virtual machine in one rack unit to a virtual machine in another rack unit. These packets may be routed between corresponding ToR switch devices and the intermediary spine switch. The ToR switches are configured to store address information associated with the host devices in the data center environment. An important aspect of network orchestration is to instantiate network elements for a tenant network on-demand and to reclaim them after their use is completed.